//这段代码使用深度优先搜索（DFS）的方法，在字符串 s 中找出所有与字符串 t 相同的非连续子序列的个数。

void dfs(int cur,int length, int& res, const string& s,const string& t, string& tmp)
{
	if (cur >= length)
	{
		return;
	}
	for (int i = cur;i < length;++i)
	{
		tmp.push_back(s[i]);
		if (tmp == t)
		{
			++res;
			goto end;
		}
		dfs(cur + 1, length, res, s, t, tmp);
end:
		tmp.pop_back();
	}
}
int func(const string& s, const string& t)
{
	int res = 0;
	int length = s.size();
	string tmp = "";
	dfs(0, length, res, s, t, tmp);
	return res;
}



//栈和排序

vector<int> solve(vector<int>& v) //1-n数据
{
	int size = v.size();
	int index = 0;
	int tmp = size;
	stack<int> st;
	vector<int> res;
	bool arr[size + 1] = { false };
	while (index < size)
	{
		st.push(v[index]);
		arr[v[index]] = true;
		while (arr[tmp])
		{
			--tmp;
		}
		while (!st.empty() && st.top() >= tmp)
		{
			res.push_back(st.top());
			st.pop();
		}
		++index;
	}
	return res;
}


//拓扑排序（有向无环图）
vector<int> topologicalSort(const vector<vector<int>>& vv)
{
	int n = vv.size();
	vector<int> judge(n, 0); //存储图中的每个顶点的入度
	for (auto& e : vv) //计算每个顶点的度
	{
		int size = e.size();
		for (int i = 0;i < size;++i)
		{
			judge[e[i]]++;
		}
	}
	vector<int> res; //存储拓扑排序后的结果
	queue<int> q;
	for (int i = 0;i < judge.size();++i) //将入度为零的顶点push到队列中
	{
		if (judge[i] == 0)
		{
			q.push(i);
		}
	}
	while (!q.empty())
	{
		int tmp = q.front();
		q.pop();
		res.push_back(tmp); //将该入度为0的顶点加入到res结果集中
		for (int i = 0;i < vv[tmp].size();++i)
		{
			if (--judge[vv[tmp][i]] == 0)
			{
				q.push(vv[tmp][i]);
			}
		}
	}
	if (res.size() != vv.size())  //说明有向有环图，无法进行拓扑排序
	{
		res.clear();
		cout << "图中存在环，无法进行拓扑排序！" << endl;
	}
	return res;
}



int main()
{
	//定义一个邻接矩阵
	vector<vector<int>> vv = {
		{},
		{2,3},
		{3},
		{}
	};

	for (auto e : topoSort(vv))
	{
		cout << e << " : ";
	}
    return 0;
}